1. Field of Invention
This invention relates generally to semiconductor memories and specifically to content addressable memories.
2. Description of Related Art
Content addressable memories (CAMs) are frequently used for address look-up functions in Internet data routing. For example, routers used by local Internet Service Providers (ISPs) typically include one or more CAMs for storing a plurality of Internet addresses and associated data such as, for instance, corresponding address routing information. When data is routed to a destination address, the destination address is compared with all CAM words, e.g., Internet addresses, stored in the CAM array. If there is a match, routing information corresponding to the matching CAM word is output and thereafter used to route the data.
A CAM device includes a CAM array having a plurality of memory cells arranged in an array of rows and columns. Each memory cell stores a single bit of digital information, i.e., either logic zero or logic one. The bits stored within a row of memory cells constitute a CAM word. During compare operations, a comparand word is received at appropriate input terminals of a CAM device and driven into the CAM array using comparand lines to be compared with all the CAM words in the device. For each CAM word that matches the comparand word, a corresponding match line signal is asserted to indicate a match condition. If the comparand word matches more than one of the CAM words, the match line corresponding to each of the matching CAM words is asserted, and a xe2x80x9cmultiple matchxe2x80x9d flag is also asserted to indicate the multiple match condition. The match line signals from each CAM block are combined in a priority encoder to determine the index or address of the highest-priority matching CAM word. Associative information corresponding to the highest-priority matching CAM word stored in, for instance, an associated RAM, may also be provided.
A single CAM device may include one or more CAM blocks, each having an array of CAM cells. In such a device, the CAM blocks typically have consecutive address spaces. When one of the CAM blocks is defective, the corresponding address space is no longer available. As a result, the entire CAM device may no longer be suitable for its intended purpose, particularly when the address spaces in the remaining, non-defective CAM blocks are non-contiguous. Rather than discarding the CAM device, it would be desirable to disable the one or more defective CAM blocks, and operate the remaining non-defective CAM blocks using contiguous address space.
A method and apparatus are disclosed that may be used to disable one or more defective CAM blocks, and to selectively re-assign priority between the remaining enabled CAM blocks. In accordance with one embodiment of the present invention, each CAM block includes an array of CAM cells organized in a number of rows and columns, where each row has a match line to indicate match conditions therein during a compare operation. Each block also includes a block priority encoder coupled to the number of match lines and having an output to provide a row index of a row that stores data that matches comparand data. The row indexes from the CAM blocks are provided to a main priority encoder that stores a dynamic block index for each of the plurality of CAM blocks. The main priority encoder combines each row index with a corresponding block index to generate a device index for each CAM block. The main priority encoder may re-assign priority between the plurality of CAM blocks by manipulating the dynamic block indexes.
In one embodiment, the main priority encoder includes select logic and a multiplexer chain. The multiplexer chain includes a plurality of multiplexers each having a first input coupled to an output of a previous multiplexer, a second input to receive the row index and block index from a corresponding CAM block, an output coupled to a first input of a next multiplexer, and a select terminal. The select logic is coupled to receive match information from the CAM blocks and in response thereto provides select signals to the plurality of multiplexers.